This invention relates to dispersal and reconstruction of information during communication or storage and retrieval, in order to achieve fault tolerance and load balancing.
When information is communicated or stored, it may be lost if the communication link or storage medium fails. One straightforward, but inefficient, way to reduce the chance of loss is simply to transmit duplicate copies of the information over different communication links or to store duplicate copies in different storage locations. By providing enough duplicate copies, the likelihood that all copies will be lost can be made as small as desired. But this fault tolerance is achieved only at great cost in transmission or storage resources.
Asmuth, et al., "Pooling, splitting, and restituting information to overcome total failure of some channels of communication," Proc. of the 1982 Symp. on Security and Privacy, IEEE Soc. (1982), pp. 156-169, propose an algorithm for splitting and restituting information that applies to specific small cases of the problem, and is based on number theoretic computations, namely the Chinese remaindering method.
Conventional error correction codes add extra bits to a binary message to create a block such that any k errors (bit reversals or lost bits) that occur in the block during transmission or storage can be corrected.